package hero.mps.leet_code_4;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
 */

public class FindMedianSortedArrays {


    public static void main(String[] args) {
        int[] array1 = {1, 2};
        int[] array2 = {3, 4};

        System.out.println(findMedianSortedArraysGetKth(array1, array2));
    }
    /**
     * 计算两个已排序数组的中位数
     *
     * @param nums1 第一个已排序数组
     * @param nums2 第二个已排序数组
     * @return 两个数组的中位数
     */
    private static Double findMedianSortedArraysByMerge(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        // 初始化两个指针分别指向两个数组的起始位置
        int left = 0, right = 0;

        // 初始化两个变量来存储已经遍历过的较小值的前两个数
        int prevSmaller = -1, currSmaller = -1;
        boolean flag = (m + n) % 2 == 0;

        // 遍历两个数组，直到找到一个或者两个较小值
        for (int k = 0; k <= (m + n) / 2; k++) {
            currSmaller = prevSmaller;
            // 根据当前两个指针指向的值的大小关系移动指针
            if (left < m && (right >= n || nums1[left] < nums2[right])) {
                prevSmaller = nums1[left++];
            } else {
                prevSmaller = nums2[right++];
            }
        }
        if (flag) {
            return (prevSmaller + currSmaller) / 2.0;
        }

        // 如果数组总长度为偶数，且上面的循环没有返回，则直接返回prevSmaller（即两个较小值中的后一个）
        return prevSmaller * 1.0;
    }

    public static double findMedianSortedArraysGetKth(int[] nums1, int[] nums2) {
        int ans1 = getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, (nums1.length + nums2.length + 1) / 2);
        int ans2 = getKth(nums1,0, nums1.length - 1, nums2, 0, nums2.length - 1, (nums1.length + nums2.length + 2) / 2);
        //如果是奇数，则两次求的k都是一样的，即(nums1.length + nums2.length + 1) / 2 == (nums1.length + nums2.length + 2) / 2
        return (ans1 + ans2) / 2.0;
    }
    public static int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        // 计算nums1数组的长度
        int size1 = end1 - start1 + 1;
        // 计算nums2数组的长度
        int size2 = end2 - start2 + 1;

        // 如果nums1数组的长度大于nums2数组的长度，则交换两个数组以及对应的起始和结束索引，然后递归调用函数
        if (size1 > size2) {
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }

        // 如果nums1数组为空，则返回nums2数组中第k个元素（索引为start2+k-1）
        if (size1 == 0) {
            return nums2[start2 + k - 1];
        }

        // 如果k为1，则返回nums1和nums2的起始元素中的较小值
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }

        // 计算nums1数组中第k/2个元素的索引
        int pos1 = start1 + Math.min(k / 2, size1) - 1;
        // 计算nums2数组中第k/2个元素的索引
        int pos2 = start2 + Math.min(k / 2, size2) - 1;

        // 如果nums1数组中第k/2个元素大于nums2数组中第k/2个元素
        if (nums1[pos1] > nums2[pos2]) {
            // 递归调用函数，从nums1数组中的起始索引到结束索引，以及nums2数组中pos2+1到end2的范围内寻找第k-(pos2-start2+1)个元素
            return getKth(nums1, start1, end1, nums2, pos2 + 1, end2, k - (pos2 - start2 + 1));
        // 如果nums1数组中第k/2个元素小于等于nums2数组中第k/2个元素
        }else {
            // 递归调用函数，从nums1数组中pos1+1到end1的范围内，以及nums2数组中的起始索引到结束索引的范围内寻找第k-(pos1-start1+1)个元素
            return getKth(nums1, pos1 + 1, end1, nums2, start2, end2, k - (pos1 - start1 + 1));
        }
    }

    /**
     * 计算两个已排序数组的中位数
     *
     * @param nums1 第一个已排序数组
     * @param nums2 第二个已排序数组
     * @return 两个数组的中位数
     */
    private static Double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] newArray = new int[nums1.length + nums2.length];
        int index = 0;
        for (int element : nums1) {
            newArray[index++] = element;
        }
        for (int element : nums2) {
            newArray[index++] = element;
        }
        Arrays.sort(newArray);
        Double median = 0.0;
        if (newArray.length % 2 == 0) {
           median = (newArray[newArray.length / 2] + newArray[newArray.length / 2 - 1]) / 2.0;
        }else {
            median = newArray[newArray.length / 2] / 1.0;
        }
        return median;
    }

}
